#include "biTree.h"

/**
 * 功 能：
 *      创建并且初始二叉树 - 按照先序遍历建立二叉树
 * 参 数：
 *      无
 * 返回值：
 *      成功：创建完成的树的根节点
 *      失败：NULL
 **/
BiTNode *BiTree_Create()
{
    BiTNode *root = NULL;
    char ch;

    scanf("%c", &ch);

    // 如果字符值不为 # ，则说明节点存在
    if (ch != '#')
    {
        // 为节点申请空间
        root = (BiTNode *)malloc(sizeof(BiTNode));
        if (root == NULL)
            return NULL;

        memset(root, 0, sizeof(BiTNode));

        // 将字符值赋值给节点
        root->data = ch;
        // 递归创建左孩子，并将返回值赋值给左孩子
        root->lchild = BiTree_Create(root);
        // 递归创建右孩子，并将返回值赋值给右孩子
        root->rchild = BiTree_Create(root);
        // 返回根节点
    }
    // else // 符值为 #, 节点存在为空，返回为空
    // {
    //     root = NULL;
    // }

    return root;
}

/**
 * 功 能：
 *      二叉树节点释放
 * 参 数：
 *      tree：要释放的二叉树
 * 返回值：
 *      无
 **/
void BiTree_Release(BiTNode *tree)
{
    if (tree == NULL)
        return;

    // 递归释放左孩子节点
    if (tree->lchild != NULL)
    {
        BiTree_Release(tree->lchild);
        tree->lchild = NULL;
    }

    // 递归释放右孩子节点
    if (tree->rchild != NULL)
    {
        BiTree_Release(tree->rchild);
        tree->rchild = NULL;
    }

    // 释放根节点
    if (tree != NULL)
    {
        free(tree);
        tree = NULL;
    }
}

/**
 * 功 能：
 *      二叉树的先序遍历
 * 参 数：
 *      root：要遍历的树
 * 返回值：
 *      无 
 **/
void Traversal_Before(BiTNode *root)
{
    if (root == NULL)
        return;
    // 遍历根节点
    printf("%c ", root->data);
    // 遍历左子树
    Traversal_Before(root->lchild);
    // 遍历右子树
    Traversal_Before(root->rchild);
}

/**
 * 功 能：
 *      二叉树的中序遍历
 * 参 数：
 *      root：要遍历的树
 * 返回值：
 *      无 
 **/
void Traversal_Middle(BiTNode *root)
{
    if (root == NULL)
        return;

    // 遍历左子树
    Traversal_Middle(root->lchild);
    // 遍历根节点
    printf("%c ", root->data);
    // 遍历右子树
    Traversal_Middle(root->rchild);
}
/**
 * 功 能：
 *      二叉树的后序遍历
 * 参 数：
 *      root：要遍历的树
 * 返回值：
 *      无 
 **/
void Traversal_Later(BiTNode *root)
{
    if (root == NULL)
        return;

    // 遍历左子树
    Traversal_Later(root->lchild);
    // 遍历右子树
    Traversal_Later(root->rchild);
    // 遍历根节点
    printf("%c ", root->data);
}

/**
 * 功 能：
 *      求出二叉树的深度/高度
 * 参 数：
 *      root：要求高度的树
 * 返回值：
 *      无 
 **/
int CounterBiTreeDepth(BiTNode *root)
{
    int left = 0;
    int right = 0;
    int value = 0;

    if (root == NULL)
    {
        value = 0;
        return value;
    }
    // 左子树的高度
    left = CounterBiTreeDepth(root->lchild);
    // 右子树的高度
    right = CounterBiTreeDepth(root->rchild);
    // 左子树的高度 或者 右子树高度 + 1
    value = 1 + (left > right ? left : right);

    return value;
}

/**
 * 功 能：
 *      二叉树的递归遍历 - 第i层的遍历
 * 参 数：
 *      root：要遍历的树
 *      i   ：要遍历的层
 * 返回值：
 *      无 
 **/
void _Traversal_Level(BiTNode *root, int i)
{
    if (root == NULL || i == 0)
        return;
    if (i == 1)
    {
        printf("%c ", root->data);
        return;
    }
    _Traversal_Level(root->lchild, i - 1);
    _Traversal_Level(root->rchild, i - 1);
}

/**
 * 功 能：
 *      二叉树的递归遍历 - 层序遍历
 * 参 数：
 *      root：要遍历的树
 * 返回值：
 *      无 
 **/
void Traversal_Level(BiTNode *root)
{
    int i = 0;
    if (root == NULL)
        return;
    int dep = CounterBiTreeDepth(root); // BTreeDepth(root);
    for (i = 1; i <= dep; i++)
    {
        _Traversal_Level(root, i);
    }
}

/**
 * 功 能：
 *      求出二叉树的叶子节点的个数
 * 参 数：
 *      root：要操作的树
 *      num ：叶子节点的个数的返回值
 *            注意：不能为NULL！
 * 返回值：
 *      成功：叶子节点的个数
 *      失败：-1 
 **/
int CounterBiTreeLeaves(BiTNode *root, int *num)
{
    int tmpnum = 0;
    if (root)
    {
        if (root->lchild == NULL && root->rchild == NULL)
        {
            (*num)++;
        }
        if (root->lchild)
        {
            CounterBiTreeLeaves(root->lchild, num);
        }
        if (root->rchild)
        {
            CounterBiTreeLeaves(root->rchild, num);
        }
    }
    else
    {
        return -1;
    }
    tmpnum = *num;
    return tmpnum;
}

/**
 * 功 能：
 *      复制一个二叉树
 * 参 数：
 *      tree：要复制的树
 * 返回值：
 *      成功：复制之后的树的根节点
 *      失败：NULL
 **/
BiTNode *CopyBiTree(BiTNode *tree)
{
    BiTNode *newNode = NULL;
    BiTNode *newLeft = NULL;
    BiTNode *newRight = NULL;

    if (tree == NULL)
    {
        return NULL;
    }
    // 复制左子树
    if (tree->lchild != NULL)
    {
        newLeft = CopyBiTree(tree->lchild);
    }
    else
    {
        newLeft = NULL;
    }
    // 复制右子树
    if (tree->rchild != NULL)
    {
        newRight = CopyBiTree(tree->rchild);
    }
    else
    {
        newRight = NULL;
    }

    // malloc 根节点
    newNode = (BiTNode *)malloc(sizeof(BiTNode));

    memset(newNode, 0, sizeof(BiTNode));

    if (newNode == NULL)
        return NULL;

    // 左孩子和右孩子链接
    newNode->lchild = newLeft;
    newNode->rchild = newRight;
    newNode->data = tree->data;

    return newNode;
}

/**
 * 功 能：
 *      二叉树的节点个数
 * 参 数：
 *      tree：要操作的树
 * 返回值：
 *      成功：节点的个数
 *      失败：0
 **/
static int CounterBiTreeNodes(BiTNode *root) // O(n)
{
    int ret = 0;

    if (root != NULL)
    {
        ret = CounterBiTreeNodes(root->lchild) + CounterBiTreeNodes(root->rchild) + 1;
    }

    return ret;
}
func_BiTree fBiTree = {
    BiTree_Create,
    Traversal_Before,
    Traversal_Middle,
    Traversal_Later,
    Traversal_Level,
    CounterBiTreeLeaves,
    CounterBiTreeDepth,
    CounterBiTreeNodes,
    CopyBiTree,
    BiTree_Release};
